package 数组N连And四边形不等式And区间和问题;

public class leetcode连续子数组的最大和问题 {

	
	
	
	
	
	
	/**
	 * 正确的 dp
	 * 这个题 理解了 是真的 简单!
	 * 但是不理解 是真的 有点难受!
	 * 不要的 一味的 依赖 与  暴力递归 ,才能 改 dp
	 * 一旦 写不出来 暴力递归 ,那 dp 你就写不出来!
	 */
	
	public int rightDP(int nums[]) {
		int len = nums.length;
		int ans = nums[0], max = nums[0];
		
		for(int i = 1;i < len ;i++) {
//			max = max > 0 ? max + nums[i] : nums[i];
			max = Math.max(max + nums[i],nums[i]);
			ans = Math.max(ans, max);
		}
		return ans;
	}

	
	/**
	 * 暴力 O（N ^ 2）
	 */
	public int solution(int nums[]) {
		int ans = Integer.MIN_VALUE;
		int len = nums.length;
		for(int i = 0;i < len;i++ ) {
			int sum = 0;
			for(int j = i ;j < len ;j++)  {
				sum += nums[j];
				ans = Math.max(ans, sum);
			}
		}
		return ans;
	}
	
	/**
	 * 思想是很正确的
	 * 这个分析的过程
	 * 但是这是错的
	 */
	// wrong answer!
	public int dp(int nums[]) {
		int ans = nums[0],sum = nums[0];
		int len = nums.length;
		for(int i = 1;i < len ;i++) {
			sum += nums[i];
			ans = Math.max(ans, Math.max(sum, nums[i]));
		}
		return  ans;
	}
	
	
	
	
}
